package src.leetcode.everyday.hard_0149;

import java.util.HashSet;
import java.util.Set;

/**
 * @author liyizzz
 * @description 直线上最多的点数
 * @date 2024/12/17 11:10
 */
public class maxPoints {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxPoints(new int[][]{{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}}));
    }
}

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n < 3) return n;
        boolean[][] used = new boolean[n][n];
        int ans = 0;
        for (int i = 0; i < n - ans; i++) {
            for (int j = i + 1; j < n; j++) {
                if (used[i][j]) continue;
                int count = 2;
                for (int k = j + 1; k < n; k++) {
                    if (isLine(points[i], points[j], points[k])) {
                        count++;
                        used[i][j] = true;
                        used[i][k] = true;
                        used[j][k] = true;
                    }
                }
                ans = Math.max(ans, count);
            }
        }
        return ans;
    }

    private boolean isLine(int[] p1, int[] p2, int[] p3) {
        int s1 = (p1[1] - p2[1]) * (p1[0] - p3[0]);
        int s2 = (p1[1] - p3[1]) * (p1[0] - p2[0]);
        return s1 == s2;
    }
}